// 基础的几何算法

import { Vector2, seededRandom } from './_imports'
import type { StyleParsed, MagizTypes, Temp } from './_imports'

export {
  seed,
  sRand,
  sSample,
  sShuffleArray,
  sRandBetween,
  getBounds,
  getMatchRatioAndCount,
  isAlongAxis,
  isParallel,
  isPerpendicular,
  isPointInPolygon,
  crossLines,
  lineInsideRect,
  projectPointOnRay,
  projectPointOnLine,
  offsetRay,
  rayIntersectLine,
  rayIntersectRay,
  sweepPolygonAlongX,
  getClampedRects,
  getLoopNext,
  getValidIndexes,
}

/** 生成一个1000以内的随机正整数 */
function r1000() {
  return Math.round(Math.random() * 1000)
}

/** 自增随机数种子 */
const seed = {
  /** 预设值，用于重置 */
  _v: r1000(),
  /** 递增数值并返回 */
  get v() {
    return this._v < Number.MAX_SAFE_INTEGER ? this._v++ : (this._v = r1000())
  },
  /** 重置为指定数值，或随机值 */
  set(x: number) {
    return (this._v = x)
  },
}

/** 基于种子的随机数 */
function sRand() {
  return seededRandom(seed.v)
}

/** 数组随机采样。如果数量小于2直接返回 a[0]。如果有种子则按种子随机数采样 */
function sSample<T>(a: T[]) {
  let i = Math.floor(sRand() * a.length)
  return a[i < a.length ? i : 0]
}

/** 基于种子将数组顺序打乱，返回原数组 */
function sShuffleArray<T>(array: T[]) {
  return array.sort(() => sRand() - 0.5)
}

/** 基于种子的区间随机数 */
function sRandBetween(a: number, b: number, step?: number) {
  return step ? a + Math.floor(((b - a) / step) * sRand()) * step : a + (b - a) * sRand()
}

/** 根据点积计算定界框的最小点和最大点，如有轴向长度为0返回空值 */
function getBounds(XYLoop?: MagizTypes.XY[]): MagizTypes.bounds | undefined {
  const pt = XYLoop?.[0]
  if (pt) {
    const min = { ...pt }
    const max = { ...pt }
    XYLoop.forEach((XY) => {
      const { x, y } = XY
      x < min.x ? (min.x = x) : x > max.x ? (max.x = x) : 0
      y < min.y ? (min.y = y) : y > max.y ? (max.y = y) : 0
    })
    if (Math.round((max.x - min.x) * 1000000) > 0 && Math.round((max.y - min.y) * 1000000) > 0)
      return { min, max }
  }
  return undefined
}

/** 根据边与X轴间的弧度判断是否为东西向 */
function isAlongAxis(r: number): boolean {
  return r < 0.7854 || r > 5.4978 || (2.3562 < r && r < 3.927)
}

/** 计算线段与线段的交点（包括端点），排除平行的情况 */
function crossLines(line1: Temp.Line, line2: Temp.Line): Vector2 | undefined {
  const { x: x1, y: y1 } = line1.start
  const { x: x2, y: y2 } = line1.end
  const { x: x3, y: y3 } = line2.start
  const { x: x4, y: y4 } = line2.end

  const d = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)
  // d值判断是否平行
  if (d !== 0) {
    const t = ((x1 - x3) * (y3 - y4) - (y1 - y3) * (x3 - x4)) / d
    const u = -((x1 - x2) * (y1 - y3) - (y1 - y2) * (x1 - x3)) / d
    // 判断是否在各自的线段之上，包括端点
    if (t >= 0 && t <= 1 && u >= 0 && u <= 1) {
      return new Vector2(x1 + t * (x2 - x1), y1 + t * (y2 - y1))
    }
  }

  return undefined
}

/** 检测线段与线段是否相交，包括端点和线段之上 */
function isPointInRect(point: Vector2, rectangle: Temp.Rectangle) {
  const { x, y } = point
  return (
    x >= rectangle.min.x && x <= rectangle.max.x && y >= rectangle.min.y && y <= rectangle.max.y
  )
}

/** 计算 line 与 box 相交的部分，返回新线段或 undefined */
function lineInsideRect(line: Temp.Line, rectangle: Temp.Rectangle): Temp.Line | undefined {
  // start 和 end 不会相同
  const pointsInside = [line.start, line.end].filter((point) => isPointInRect(point, rectangle))
  const insideCount = pointsInside.length

  // 位于在框内、边线上、端点的点的数量
  if (insideCount === 2) {
    return { start: line.start.clone(), end: line.end.clone() }
  } else {
    // 计算包括交于端点情况在内的交点
    const intersections: Vector2[] = []
    rectangle.lines.forEach((l) => {
      const i = crossLines(l, line)
      if (i) intersections.push(i)
    })
    const pt = pointsInside[0]
    const i = intersections[0]
    const i1 = intersections[1]

    if (pt) {
      if (i) {
        if (i && i1) {
          // 有1个非外部点和2交点，返回两个交点
          return getSameDirection(line, i, i1)
        } else {
          // 有1个非外部点则至少有1交点，须排除非外部点位于边线上时的情况
          if (i.x !== pt.x || i.y !== pt.y) return getSameDirection(line, i, pt)
        }
      }
    } else if (i && i1 && (i.x !== i1.x || i.y !== i1.y)) {
      // 有0个非外部点，可能两个交点，交于端点时两个交点相同，须排除
      return getSameDirection(line, i, i1)
    }
  }
  return undefined
}

/** 通过计算点积，返回由p1和p2组成的与line1方向一致的新线段 */
function getSameDirection(line1: Temp.Line, p1: Vector2, p2: Vector2): Temp.Line {
  const direction1 = { x: line1.end.x - line1.start.x, y: line1.end.y - line1.start.y }
  const direction2 = { x: p2.x - p1.x, y: p2.y - p1.y }
  return direction1.x * direction2.x + direction1.y * direction2.y > 0
    ? { start: p1, end: p2 }
    : { start: p2, end: p1 }
}

// 根据公式 P = A + ((B - A) · (P - A)) / ||B - A||^2 * (B - A)
/** 计算点在线段上的投影点，不含线段的端点！ */
function projectPointOnLine(point: Vector2, line: Temp.Line): Vector2 | undefined {
  const { start, end } = line
  const PA = new Vector2().subVectors(point, start)
  const BA = new Vector2().subVectors(end, start)
  const t = PA.dot(BA) / BA.lengthSq()

  return t > 0 && t < 1 ? new Vector2(start.x + t * BA.x, start.y + t * BA.y) : undefined
}

/** 计算点在射线上的投影点 */
function projectPointOnRay(point: Vector2, ray: Temp.Ray): Vector2 {
  const { start, direction } = ray
  const PA = new Vector2().subVectors(point, start)
  const t = PA.dot(direction) / direction.lengthSq()
  return new Vector2(start.x + t * direction.x, start.y + t * direction.y)
}

function rayIntersectLine(ray: Temp.Ray, line: Temp.Line): Vector2 | undefined {
  const { x: sx, y: sy } = ray.start
  const { x: dx, y: dy } = ray.direction
  const { x: lsx, y: lsy } = line.start
  const rx = line.end.x - lsx
  const ry = line.end.y - lsy
  const r = dx * ry - dy * rx
  // Not parallel lines
  if (r !== 0) {
    const qmp = { x: lsx - sx, y: lsy - sy }
    const t = (qmp.x * ry - qmp.y * rx) / r
    const u = (qmp.x * dy - qmp.y * dx) / r

    if (t >= 0 && u >= 0 && u <= 1) {
      return new Vector2(sx + t * dx, sy + t * dy)
    }
  }
  return
}

function rayIntersectRay(ray1: Temp.Ray, ray2: Temp.Ray): Vector2 | undefined {
  const { x: sx1, y: sy1 } = ray1.start
  const { x: dx1, y: dy1 } = ray1.direction
  const { x: sx2, y: sy2 } = ray2.start
  const { x: dx2, y: dy2 } = ray2.direction
  const r = dx1 * dy2 - dy1 * dx2
  // Not parallel lines
  if (r !== 0) {
    const qmp = { x: sx2 - sx1, y: sy2 - sy1 }
    const t = (qmp.x * dy2 - qmp.y * dx2) / r
    return new Vector2(sx1 + t * dx1, sy1 + t * dy1)
  }
  return
}

/** 按轴向偏移射线 */
function offsetRay(ray: Temp.Ray, offsetParams: { x: number; y: number }): Temp.Ray {
  const { x, y } = ray.direction
  // 通过向量点积公式可得与之垂直的向量为[y,-x]或[-y,x]
  const crossV = new Vector2(y, -x)
  crossV.setLength(isAlongAxis(crossV.angle()) ? offsetParams.x : offsetParams.y)
  const start = crossV.add(ray.start)
  return {
    start,
    end: start.clone().add(ray.direction),
    direction: ray.direction,
  }
}

/** 根据叉积判断Vector2是否平行 */
function isParallel(v1: Vector2, v2: Vector2): boolean {
  return v1.x * v2.y - v1.y * v2.x === 0
}

/** 根据点积判断Vector2是否垂直 */
function isPerpendicular(v1: Vector2, v2: Vector2): boolean {
  return v1.x * v2.x + v1.y * v2.y === 0
}

/** 使用射线法判断点是否在多边形内部 */
function isPointInPolygon(point: Vector2, polygon: Vector2[]): boolean {
  let inside = false
  for (let i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
    const { x: xi, y: yi } = polygon[i]!
    const { x: xj, y: yj } = polygon[j]!
    const intersect =
      yi > point.y !== yj > point.y && point.x < ((xj - xi) * (point.y - yi)) / (yj - yi) + xi
    if (intersect) inside = !inside
  }
  return inside
}

/** 返回多边形内部的随机点，采样的方式运算效率较低。另有画线与面向交并计算相交线段内的点的方法 */

/** 计算用间距组合拟合指定长度的缩放系数 */
function getMatchRatioAndCount(
  /** 用于拟合的基准间距组合 */
  spaces: number[],
  /** 拟合对标的总长度 */
  distance: number,
  /** 生成时从起点偏移的距离 */
  endWidth: undefined | number,
  /** 在终点生成与首位相同的元素。同时也会计算尽端的endWidth，可通过endWidth对齐尽端 */
  sandwich: StyleParsed.Bool
) {
  const totalSpace = spaces.reduce((v, s) => v + s, 0)
  if (totalSpace > 0) {
    endWidth = endWidth || 0
    const count = Math.round(distance / totalSpace)
    const total = totalSpace * count + (sandwich ? endWidth * 2 : endWidth)
    if (count > 0) {
      return { ratio: distance / total, count }
    }
  }
  return undefined
}

/** 计算平行X轴的直线与多边形所有边的交点，排除在端点的情况，结果按x值从小到大排序，可能出现多对线段 */
function sweepPolygonAlongX(y: number, lines: Temp.Line[]): Temp.Line[] {
  /** 沿水平方向计算交叉点的简易方法，不包括线段的端点，排除直线与多边线交点为奇数的情况 */
  function pointInLineAtY(line: Temp.Line, y: number): Vector2 | undefined {
    const { x: sx, y: sy } = line.start
    const { x: ex, y: ey } = line.end
    if (sy < ey ? sy < y && y < ey : ey < y && y < sy) {
      const k = (ey - sy) / (ex - sx)
      const x = (y - sy) / k + sx
      return new Vector2(x, y)
    }
    return
  }

  const result: Temp.Line[] = []
  const a: Vector2[] = []
  lines.forEach((line) => {
    const pt = pointInLineAtY(line, y)
    if (pt) a.push(pt)
  })

  // 边的排序无规律导致交点无规律，须按x值从小到大排序
  a.sort((a, b) => a.x - b.x)
  // 保证成对

  for (let i = 0; i < a.length; i += 2) {
    const a1 = a[i]
    const a2 = a[i + 1]
    // 成对推送到结果
    if (a1 && a2) result.push({ start: a1, end: a2 })
  }
  return result
}

/** 根据参数返回偏移后的定界框 */
function getClampedRects(
  bounds: MagizTypes.bounds,
  params: StyleParsed.ClampType
): MagizTypes.bounds[] {
  const min = { ...bounds.min }
  const max = { ...bounds.max }
  const w = max.x - min.x
  const h = max.y - min.y
  const { startX, endX, startY, endY, asRatio, reverse } = params
  const result = [{ min, max }]

  setClamped(result, w, 'x', startX, endX, asRatio, reverse)
  setClamped(result, h, 'y', startY, endY, asRatio, reverse)

  return result
}

/** 按参数生成修改原 bounds 中定界框的坐标 */
function setClamped(
  bounds: MagizTypes.bounds[],
  distance: number,
  axis: 'x' | 'y',
  start: number,
  end: number,
  asRatio: StyleParsed.Bool,
  reverse: StyleParsed.Bool
): void {
  if (start || end) {
    const dStart = start ? (asRatio ? start * distance : start) : 0
    const dEnd = end ? (asRatio ? end * distance : end) : 0
    bounds.forEach((rect) => {
      if (reverse) {
        if (dStart && dEnd) {
          // 反向两端同时缩进，新增一个矩形
          const newRect = { min: { ...rect.min }, max: { ...rect.max } }
          bounds.push(newRect)
          // 修改矩形数据
          newRect.min[axis] = newRect.max[axis] - dEnd
          rect.max[axis] = rect.min[axis] + dStart
        } else if (dStart) {
          rect.max[axis] = rect.min[axis] + dStart
        } else if (dEnd) {
          rect.min[axis] = rect.max[axis] - dEnd
        }
      } else {
        rect.min[axis] += dStart
        rect.max[axis] -= dEnd
      }
    })
  }
}

function getLoopNext<T>(a: T[], i: number) {
  let nextID = i + 1
  if (nextID >= a.length) nextID = 0
  return a[nextID]!
}

/** 基于种子和控制器，计算需生成元素的序号 */
function getValidIndexes(count: number, control: StyleParsed.IndexController | undefined) {
  let result: number[] = []
  if (control) {
    const { total, indent, filter, chance } = control
    if (total > 0) count = total
    if (indent) {
      indentIndexes(count, indent, result)
    } else {
      for (let i = 0; i < count; i++) result.push(i)
    }

    const filterSteps = filter?.reduce((v, f) => v + Math.abs(f), 0) || 0
    if (filter && filterSteps > 0) {
      result = result.filter((_, i) => {
        let fid = i % filterSteps
        const found = filter.find((f) => {
          const step = Math.abs(f)
          if (fid < step) {
            return true
          } else {
            fid -= step
            return false
          }
        })
        return !found || found > 0
      })
    }

    if (chance > 0) {
      result = result.filter(() => sRand() < chance)
    }
  } else {
    for (let i = 0; i < count; i++) result.push(i)
  }
  return result
}

function indentIndexes(total: number, indent: StyleParsed.IndentType, result: number[]) {
  let startID = 0
  let endID = total - 1
  const { central, asRatio, reverse, start, end } = indent

  if (start) {
    const dStart = asRatio ? Math.round(total * start) : start
    startID = central ? Math.round((total - 1) / 2.0 - dStart) : dStart
  }
  if (end) {
    const dEnd = asRatio ? Math.round(total * end) : end
    endID = central ? Math.round((total - 1) / 2.0 + dEnd) : total - 1 - dEnd
  }

  if (reverse) {
    for (let i = 0; i < startID; i++) result.push(i)
    for (let i = endID + 1; i < total; i++) result.push(i)
  } else {
    for (let i = startID; i <= endID; i++) result.push(i)
  }
}
